#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;

//template<class K>
//struct FuncHash
//{
//	size_t operator()(const K& key)
//	{
//		return size_t key;
//	}
//};
//
//template<>
//struct FuncHash<string>
//{
//	size_t operator()(const string& s)
//	{
//		size_t hash = 0;
//		for (auto ch : s)
//		{
//			hash += ch;
//			hash * 131;
//		}
//		return hash;
//	}
//};

template<class K,class V>
struct HashNode
{
	pair<K, V> _kv;
	HashNode<K, V>* _next;

	HashNode(const pair<K,V> kv)
		:_kv(kv)
		,_next(nullptr)
	{}
};

inline unsigned long __stl_next_prime(unsigned long n)
{
	static const int __stl_num_primes = 28;
	static const unsigned long __stl_prime_list[__stl_num_primes] = {
		53, 97, 193, 389, 769,
		1543, 3079, 6151, 12289, 24593,
		49157, 98317, 196613, 393241, 786433,
		1572869, 3145739, 6291469, 12582917, 25165843,
		50331653, 100663319, 201326611, 402653189, 805306457,
		1610612741, 3221225473, 4294967291
	};
	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list + __stl_num_primes;
	const unsigned long* pos = lower_bound(first, last, n);
	return pos == last ? *(last - 1) : *pos;
}

template<class K,class V/*class Hash=FuncHash<K>*/>
class HashTable
{
	typedef HashNode<K, V> Node;
public:
	HashTable()
		:_tables(__stl_next_prime(0))
		,_n(0)
	{}

	~HashTable()
	{
		for (size_t i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}

			_tables[i] = nullptr;
		}
	}
	bool Insert(const pair<K, V>& kv)
	{
		if(Find(kv.first))
			return false;
		/*Hash hs;*/
		if (_n == _tables.size())
		{
			vector<Node*>NewTable(__stl_next_prime(_tables.size() + 1));
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					size_t hashi = cur->_kv.first % _tables.size();
					Node* next = cur->_next;
					cur->_next = _tables[hashi];
					_tables[hashi] = cur;

					cur = next;
				}

				_tables[i] = nullptr;
			}

			_tables.swap(NewTable);
		}
		size_t hashi = kv.first % _tables.size();
		Node* newnode = new Node(kv);
		newnode->_next = _tables[hashi];
		_tables[hashi] = newnode;

		++_n;
		return true;
	}

	Node* Find(const K& key)
	{
		/*Hash hs;*/
		size_t hashi = key % _tables.size();
		Node* cur = _tables[hashi];
		while (cur)
		{
			if (cur->_kv.first == key)
			{
				return cur;
			}
			else
			{
				cur = cur->_next;
			}
		}
		return nullptr;
	}
	bool Erase(const K& key)
	{
		/*Hash hs;*/
		size_t hashi = key % _tables.size();
		Node* prev = nullptr;
		Node* cur = _tables[hashi];
		while (cur)
		{
			if (cur->_kv.first == key)
			{
				if (prev == nullptr)
				{
					_tables[hashi] = cur->_next;
				}
				else
				{
					prev->_next = cur->_next;
				}

				delete cur;
				--_n;
				return true;
			}
			else
			{
				prev = cur;
				cur = cur->_next;
			}
		}

		return false;
	}
private:
	vector<Node*> _tables;
	size_t _n;
};
